home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Compilers⁄Interps / little-c / Little_C.c < prev    next >
C/C++ Source or Header  |  1993-10-04  |  15KB  |  575 lines
  1. /* A Little C interpreter. 
  2.   
  3.    Herbert Schildt, "Building your own C interpreter."
  4.    Dr. Dobb's Journal of Software Tools v14, n8 (August, 1989):38 (16 pages).
  5. */
  6.  
  7. #include <stdio.h>
  8. #include <setjmp.h>
  9. #include <math.h>
  10. #include <ctype.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13.  
  14. #ifdef MACINTOSH
  15. #include <console.h>
  16. #endif
  17.  
  18. #define NUM_FUNC       100
  19. #define NUM_GLOBAL_VARS 100
  20. #define NUM_LOCAL_VARS  200
  21. #define NUM_BLOCK    100
  22. #define ID_LEN          31 
  23. #define FUNC_CALLS      31
  24. #define NUM_PARAMS    31
  25. #define PROG_SIZE     10000
  26. #define LOOP_NEST    31
  27.  
  28. enum tok_types {DELIMITER, IDENTIFIER, NUMBER, KEYWORD, 
  29.         TEMP, STRING, BLOCK};
  30.  
  31. /* add additional C keyword tokens here */
  32. enum tokens {ARG, CHAR, INT, IF, ELSE, FOR, DO, WHILE,
  33.          SWITCH, RETURN, EOL, FINISHED, END};
  34.  
  35. /* add additional double operators here (such as ->) */
  36. enum double_ops {LT=1, LE, GT, GE, EQ, NE};
  37.  
  38. /* These are the constants used to call sntx_err() when
  39.    a syntax error occurs.  Add more if you like.
  40.    NOTE: SYNTAX is a generic error message used when
  41.    nothing else seems appropriate.
  42. */
  43. enum error_msg
  44.      {SYNTAX, UNBAL_PARENS, NO_EXP, EQUALS_EXPECTED,
  45.       NOT_VAR, PARAM_ERR, SEMI_EXPECTED,
  46.       UNBAL_BRACES, FUNC_UNDEF, TYPE_EXPECTED,
  47.       NEST_FUNC, RET_NOCALL, PAREN_EXPECTED,
  48.       WHILE_EXPECTED, QUOTE_EXPECTED, NOT_TEMP,
  49.       TOO_MANY_LVARS};
  50. char *prog;  /* current location in source code */
  51. char *p_buf; /* points to start of program buffer */
  52. jmp_buf e_buf; /* hold environment for longjmp() */
  53.  
  54. /* An array of these structures will hold the info
  55.    associated with global variables.
  56. */
  57. struct variable_type {
  58.   char var_name[ID_LEN];
  59.   int  var_type;
  60.   int  value;
  61. }  global_vars[NUM_GLOBAL_VARS];
  62. struct variable_type local_var_stack[NUM_LOCAL_VARS];
  63. struct func_type {
  64.   char func_name[ID_LEN];
  65.   char *loc;  /* location of entry point in file */
  66. } func_table[NUM_FUNC];
  67. int call_stack[NUM_FUNC];
  68. struct commands { /* keyword lookup table */
  69.   char command[20];
  70.   char tok;
  71. } table[] = { /* Commands must be entered lowercase */
  72.   "if",    IF, /* in this table. */
  73.   "else",  ELSE,
  74.   "for",   FOR,
  75.   "do",    DO,
  76.   "while", WHILE,
  77.   "char",  CHAR,
  78.   "int",   INT,
  79.   "return",RETURN,
  80.   "end",   END,
  81.   "",      END  /* mark end of table */
  82. };
  83. char token[80];
  84. char token_type, tok;
  85. int  functos;    /* index to top of function call stack */
  86. int  func_index; /* index into function table */
  87. int  gvar_index; /* index into global variable table */
  88. int  lvartos;    /* index into local variable stack */
  89. int  ret_value;  /* function return value */
  90. void print(void), prescan(void);
  91. void decl_global(void), call(void), putback(void);
  92. void decl_local(void), local_push(struct variable_type i);
  93. void eval_exp(int *value), sntx_err(int error);
  94. void exec_if(void), find_eob(void), exec_for(void);
  95. void get_params(void), get_args(void);
  96. void exec_while(void), func_push(int i), exec_do(void);
  97. void assign_var(char *var_name, int value);
  98. int  load_program(char *p, char *fname), find_var(char *s);
  99. void interp_block(void), func_ret(void);
  100. int  func_pop(void), is_var(char *s), get_token(void);
  101. char *find_func(char *name);
  102.  
  103. main(int argc, char *argv[])
  104. {
  105.   printf("Little C Interpreter\n\n");
  106.   
  107. #ifdef MACINTOSH
  108.     argc = ccommand(&argv);
  109. #endif
  110.  
  111.   if(argc!=2) {
  112.     printf("usage: Little_C <filename>\n");
  113.     exit(1);
  114.   }
  115.   /* allocate memory for the program */
  116.   if((p_buf=(char *) malloc(PROG_SIZE))==NULL) {
  117.     printf("Program buffer allocation failure.");
  118.     exit(1);
  119.   }
  120.   /* set program pointer to start of program buffer */
  121.   prog = p_buf; 
  122.   /* load the program to execute */
  123.   if(!load_program(p_buf, argv[1])) exit(1);
  124.   if(setjmp(e_buf)) exit(1); /* initialize long jump buffer */
  125.   prescan();       /* find the location of all functions
  126.                       and global variables in the program */
  127.   gvar_index = 0;  /* initialize global variable index */
  128.   lvartos = 0;     /* initialize local variable stack index */
  129.   functos = 0;     /* initialize the CALL stack index */
  130.   /* setup call to main() */
  131.   prog = find_func("main");  /* find program starting point */
  132.   prog--; /* back up to opening ( */
  133.   strcpy(token, "main");
  134.   call();  /* call main() to start interpreting */
  135.   return 0;
  136. }
  137.  
  138. /* Interpret a single statement or block of code.  When
  139.    interp_block() returns from it's initial call, the final
  140.    brace (or a return) in main() has been encountered.
  141. */
  142. void interp_block(void)
  143. {
  144.   int  value;
  145.   char block = 0;
  146.   do {
  147.     token_type = get_token();
  148.     /* If interpreting single statement, return on
  149.        first semicolon.
  150.     */
  151.     /* see what kind of token is up */
  152.     if(token_type==IDENTIFIER) { 
  153.         /* Not a keyword, so process expression. */
  154.     putback();  /* restore token to input stream for
  155.                        further processing by eval_exp() */
  156.     eval_exp(&value);  /* process the expression */
  157.         if(*token!=';') sntx_err(SEMI_EXPECTED);
  158.     }
  159.     else if(token_type==BLOCK) { /* if block delimiter */
  160.       if(*token=='{') /* is a block */
  161.     block = 1; /* interpreting block, not statement */
  162.       else
  163.         return; /* is a }, so return */
  164.     }
  165.     else /* is keyword */
  166.       switch(tok) {
  167.         case CHAR:
  168.        case INT:     /* declare local variables */
  169.           putback();
  170.       decl_local();
  171.       break;
  172.     case RETURN:  /* return from function call */
  173.       func_ret();
  174.       return; 
  175.     case IF:      /* process an if statement */
  176.       exec_if();
  177.       break;
  178.     case ELSE:    /* process an else statement */
  179.       find_eob(); /* find end of else block 
  180.              and continue execution */
  181.       break;      
  182.     case WHILE:   /* process a while loop */
  183.       exec_while();
  184.       break;
  185.         case DO:      /* process a do-while loop */
  186.       exec_do();
  187.       break;
  188.     case FOR: exec_for();
  189.       break;
  190.         case END:
  191.       exit(0);
  192.       }
  193.   } while (tok != FINISHED && block);
  194. }
  195.  
  196. /* Load a program. */
  197. load_program(char *p, char *fname)
  198. {
  199.   FILE *fp;
  200.   int  i, c;
  201.   
  202.   i = 0;
  203.   if((fp=fopen(fname, "rb"))==NULL) return 0;
  204.   while ( (c=getc(fp)) != EOF && i < PROG_SIZE)  {
  205.       *p = c; p++;  i++;
  206. #ifdef MACINTOSH
  207.       /* unfortunately, this interpreter knowns only \r\n as the end-of-line,
  208.          so I have to add a LF after a CR.   t.s.yang  10/02/93  UCB */
  209.       if (c=='\r') {
  210.          *p = '\n';
  211.          p++; i++;
  212.       }
  213. #endif            
  214.   }
  215.   *(p-2) = '\0'; /* null terminate the program */
  216.   fclose(fp);
  217.   return 1;
  218. }
  219.  
  220. /* Find the location of all functions in the program
  221.    and store global variables. */
  222. void prescan(void)
  223. {
  224.   char *p;
  225.   char temp[32];
  226.   int  brace = 0;  /* When 0, this var tells us that
  227.                       current source position is outside
  228.                       of any function. */
  229.   p = prog;
  230.   func_index = 0;
  231.   do { 
  232.     while(brace) {  /* bypass code inside functions */
  233.       get_token();
  234.       if(*token=='{') brace++;
  235.       if(*token=='}') brace--;
  236.     }
  237.     get_token();
  238.     if(tok==CHAR || tok==INT) { /* is global var */
  239.       putback();
  240.       decl_global();
  241.     }      
  242.     else if(token_type==IDENTIFIER) { 
  243.       strcpy(temp, token);
  244.       get_token();
  245.       if(*token=='(') {  /* must be assume a function */
  246.         func_table[func_index].loc = prog;
  247.         strcpy(func_table[func_index].func_name, temp);
  248.         func_index++;
  249.         while(*prog!=')') prog++;
  250.         prog++;
  251.        /* prog points to opening curly brace of function */
  252.       }
  253.       else
  254.         putback();
  255.     }
  256.     else if(*token=='{')
  257.       brace++;
  258.   } while(tok!=FINISHED);
  259.   prog = p;
  260. }
  261.  
  262. /* Return the entry point of the specified function. 
  263.    Return NULL if not found.
  264. */
  265. char *find_func(char *name)
  266. {
  267.   register int i;
  268.   for(i=0; i<func_index; i++)
  269.     if(!strcmp(name, func_table[i].func_name))
  270.       return func_table[i].loc;
  271.   return NULL;
  272. }
  273.  
  274. /* Declare a global variable. */
  275. void decl_global(void)
  276. {
  277.   get_token();  /* get type */
  278.   global_vars[gvar_index].var_type = tok;
  279.   global_vars[gvar_index].value = 0;  /* init to 0 */
  280.   do { /* process comma-separated list */
  281.     get_token();  /* get name */
  282.     strcpy(global_vars[gvar_index].var_name, token);
  283.     get_token();
  284.     gvar_index++;
  285.   } while(*token==',');
  286.   if(*token!=';') sntx_err(SEMI_EXPECTED);
  287. }
  288.  
  289. /* Declare a local variable. */
  290. void decl_local(void)
  291. {
  292.   struct variable_type i;
  293.   get_token();  /* get type */
  294.   i.var_type = tok;
  295.   i.value = 0;  /* init to 0 */
  296.   do { /* process comma-separated list */
  297.     get_token(); /* get var name */
  298.     strcpy(i.var_name, token);
  299.     local_push(i);
  300.     get_token();
  301.   } while(*token==',');
  302.   if(*token!=';') sntx_err(SEMI_EXPECTED);
  303. }
  304.  
  305. /* Call a function. */
  306. void call(void)
  307. {
  308.   char *loc, *temp;
  309.   int lvartemp;
  310.   loc = find_func(token); /* find entry point of function */
  311.   if(loc==NULL)
  312.     sntx_err(FUNC_UNDEF); /* function not defined */
  313.   else {
  314.     lvartemp = lvartos;   /* save local var stack index */
  315.     get_args();           /* get function arguments */
  316.     temp = prog;          /* save return location */
  317.     func_push(lvartemp);  /* save local var stack index */
  318.     prog = loc;           /* reset prog to start of function */
  319.     get_params();         /* load the function's parameters with
  320.                              the values of the arguments */
  321.     interp_block();       /* interpret the function */
  322.     prog = temp;          /* reset the program pointer */
  323.     lvartos = func_pop(); /* reset the local var stack */
  324.   }
  325. }
  326.  
  327. /* Push the arguments to a function onto the local
  328.    variable stack. */
  329. void get_args(void)
  330. {
  331.   int value, count, temp[NUM_PARAMS];
  332.   struct variable_type i;
  333.   count = 0;
  334.   get_token();
  335.   if(*token!='(') sntx_err(PAREN_EXPECTED);
  336.   /* process a comma-separated list of values */
  337.   do {
  338.     eval_exp(&value);
  339.     temp[count] = value;  /* save temporarily */
  340.     get_token();
  341.     count++;
  342.   } while(*token==',');
  343.   count--;
  344.   /* now, push on local_var_stack in reverse order */
  345.   for(; count>=0; count--) {
  346.     i.value = temp[count];
  347.     i.var_type = ARG;
  348.     local_push(i);
  349.   }
  350. }
  351.  
  352. /* Get function parameters. */
  353. void get_params(void)
  354. {
  355.   struct variable_type *p;
  356.   int i;
  357.  
  358.   i = lvartos-1;
  359.   do { /* process comma-separated list of parameters */
  360.     get_token();  
  361.     p = &local_var_stack[i];
  362.     if(*token!=')') {
  363.       if(tok!=INT && tok!=CHAR) sntx_err(TYPE_EXPECTED);
  364.       p->var_type = token_type;
  365.       get_token();
  366.       /* link parameter name with argument already on 
  367.      local var stack */
  368.       strcpy(p->var_name, token);
  369.       get_token();
  370.       i--;
  371.     }
  372.     else
  373.       break;
  374.   } while(*token==',');
  375.   if(*token!=')') sntx_err(PAREN_EXPECTED); 
  376. }
  377.  
  378. /* Return from a function. */
  379. void func_ret(void)
  380. {
  381.   int value;
  382.   value = 0;
  383.   /* get return value, if any */
  384.   eval_exp(&value);
  385.   ret_value = value;
  386. }
  387.  
  388. /* Push local variable */
  389. void local_push(struct variable_type i)
  390. {
  391.   if(lvartos>NUM_LOCAL_VARS)
  392.     sntx_err(TOO_MANY_LVARS);
  393.   local_var_stack[lvartos] = i;
  394.   lvartos++;
  395. }
  396.  
  397. /* Pop index into local variable stack. */
  398. func_pop(void)
  399. {
  400.   functos--;
  401.   if(functos<0) sntx_err(RET_NOCALL);
  402.   return(call_stack[functos]);
  403. }
  404.  
  405. /* Push index of local variable stack. */
  406. void func_push(int i)
  407. {
  408.   if(functos>NUM_FUNC)
  409.     sntx_err(NEST_FUNC);
  410.   call_stack[functos] = i;
  411.   functos++;
  412. }
  413.  
  414. /* Assign a value to a variable. */
  415. void assign_var(char *var_name, int value)
  416. {
  417.   register int i;
  418.  
  419.   /* first, see if it's a local variable */
  420.   for(i=lvartos-1; i>=call_stack[functos-1]; i--)  {
  421.     if(!strcmp(local_var_stack[i].var_name, var_name)) {
  422.       local_var_stack[i].value = value;
  423.       return;
  424.     }
  425.   }
  426.   if(i < call_stack[functos-1]) 
  427.   /* if not local, try global var table */
  428.     for(i=0; i<NUM_GLOBAL_VARS; i++)
  429.       if(!strcmp(global_vars[i].var_name, var_name)) {
  430.         global_vars[i].value = value;
  431.         return;
  432.       }
  433.   sntx_err(NOT_VAR); /* variable not found */
  434. }
  435.  
  436. /* Find the value of a variable. */
  437. int find_var(char *s)
  438. {
  439.   register int i;
  440.  
  441.   /* first, see if it's a local variable */
  442.   for(i=lvartos-1; i>=call_stack[functos-1]; i--) 
  443.     if(!strcmp(local_var_stack[i].var_name, token))
  444.       return local_var_stack[i].value;
  445.   /* otherwise, try global vars */
  446.   for(i=0; i<NUM_GLOBAL_VARS; i++)
  447.     if(!strcmp(global_vars[i].var_name, s))
  448.       return global_vars[i].value;
  449.   sntx_err(NOT_VAR); /* variable not found */
  450. }
  451.  
  452. /* Determine if an identifier is a variable. Return
  453.    1 if variable is found; 0 otherwise.
  454. */
  455. int is_var(char *s)
  456. {
  457.   register int i;
  458.  
  459.   /* first, see if it's a local variable */
  460.   for(i=lvartos-1; i>=call_stack[functos-1]; i--) 
  461.     if(!strcmp(local_var_stack[i].var_name, token))
  462.       return 1;
  463.   /* otherwise, try global vars */
  464.   for(i=0; i<NUM_GLOBAL_VARS; i++)
  465.     if(!strcmp(global_vars[i].var_name, s))
  466.       return 1;
  467.   return 0; 
  468. }
  469.  
  470. /* Execute an IF statement. */
  471. void exec_if(void)
  472. {
  473.   int cond;
  474.  
  475.   eval_exp(&cond); /* get left expression */
  476.   if(cond) { /* is true so process target of IF */
  477.     interp_block();
  478.   } else { /* otherwise skip around IF block and
  479.               process the ELSE, if present */
  480.     find_eob(); /* find start of next line */
  481.     get_token();
  482.     if(tok!=ELSE) {
  483.       putback();  /* restore token if
  484.                      no ELSE is present */
  485.       return;
  486.     }
  487.     interp_block();
  488.   }
  489. }
  490.  
  491. /* Execute a while loop. */
  492. void exec_while(void)
  493. {
  494.   int cond;
  495.   char *temp;
  496.  
  497.   putback();
  498.   temp = prog;        /* save location of top of while loop */
  499.   get_token();
  500.   eval_exp(&cond);    /* check the conditional expression */
  501.   if(cond)
  502.     interp_block();   /* if true, interpret */
  503.   else {  /* otherwise, skip around loop */
  504.     find_eob();
  505.     return;
  506.   }
  507.   prog = temp;  /* loop back to top */
  508. }
  509.  
  510. /*Execute a do loop. */
  511. void exec_do(void)
  512. {
  513.   int cond;
  514.   char *temp;
  515.   putback();
  516.   temp = prog;    /* save location of top of do loop */
  517.   get_token();    /* get start of loop */
  518.   interp_block(); /* interpret loop */
  519.   get_token(); 
  520.   if(tok!=WHILE) sntx_err(WHILE_EXPECTED);
  521.   eval_exp(&cond); /* check the loop condition */
  522.   if(cond) prog = temp; /* if true loop; otherwise, 
  523.                            continue on */
  524. }
  525.  
  526. /* Find the end of a block. */
  527. void find_eob(void)
  528. {
  529.   int brace;
  530.   get_token();
  531.   brace = 1;
  532.   do {
  533.     get_token();
  534.     if(*token=='{') brace++;
  535.     else if(*token=='}') brace--;
  536.   } while(brace);
  537. }
  538.  
  539. /* Execute a while loop. */
  540. void exec_for(void)
  541. {
  542.   int cond;
  543.   char *temp, *temp2;
  544.   int brace ;
  545.   get_token();
  546.   eval_exp(&cond);  /*initialization expression */
  547.   if(*token!=';')
  548.     sntx_err(SEMI_EXPECTED);
  549.   prog++; /* get past the ; */
  550.   temp = prog;
  551.   for(;;) {
  552.     eval_exp(&cond);  /* check the condition */    
  553.     if(*token!=';')
  554.       sntx_err(SEMI_EXPECTED);
  555.     prog++;           /* get past the ; */
  556.     temp2 = prog;
  557.     /* find the start of the for block */
  558.     brace = 1;
  559.     while(brace) {
  560.       get_token();
  561.       if(*token=='(') brace++;
  562.       if(*token==')') brace--;
  563.     }
  564.     if(cond)
  565.       interp_block();  /* if true, interpret */
  566.     else {  /* otherwise, skip around loop */
  567.       find_eob();
  568.       return;
  569.     }
  570.     prog = temp2;
  571.     eval_exp(&cond); /* do the increment */
  572.     prog = temp;  /* loop back to top */
  573.   } 
  574. }
  575.